package cn.nawang.ebeim.client.version;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by GanJc on 2016/2/19.
 */
public class Tree {

    private static int[] coins = new int[]{1, 3, 5};

    private static Map<Integer, Integer> cache = new HashMap<Integer, Integer>();

    private static int count = 0;

    public static int d(int n) {
        if (cache.get(n) != null) {
            return cache.get(n);
        }
        if (n == 0) {
            return 0;
        } else {
            int min = 0;
            count++;
            for (int i = 0; i < coins.length; i++) {
                if (n < coins[i]) continue;
                int e = d(n - coins[i]) + 1;
                if (i == 0) {
                    min = e;
                } else {
                    if (min > e) {
                        min = e;
                    }
                }
            }
            cache.put(n, min);
            return min;
        }
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int n = 11;
        d(n);
        System.out.println(cache.values());
        System.out.println("总耗时:" + (System.currentTimeMillis() - start) + " ms! 递归计算次数" + count);
    }


}
